package Leetcode.贪心;

import java.util.Arrays;

/**
 * @Author: kirito
 * @Date: 2024/9/26 16:22
 * @Description:
 * 给定数组 people 。people[i]表示第 i 个人的体重 ，船的数量不限，每艘船可以承载的最大重量为 limit。
 *
 * 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
 *
 * 返回 承载所有人所需的最小船数 。
 *
 * 示例 1：
 *
 * 输入：people = [1,2], limit = 3
 * 输出：1
 * 解释：1 艘船载 (1, 2)
 * 示例 2：
 *
 * 输入：people = [3,2,2,1], limit = 3
 * 输出：3
 * 解释：3 艘船分别载 (1, 2), (2) 和 (3)
 * 示例 3：
 *
 * 输入：people = [3,5,3,4], limit = 5
 * 输出：4
 * 解释：4 艘船分别载 (3), (3), (4), (5)
 */

public class 救生艇 {
    public static void main(String[] args) {
        int[] arr = {3,5,3,4};
        int limit = 5;
        救生艇 test = new 救生艇();
        System.out.println(test.numRescueBoats(arr, limit));
    }
    /**
     * 1 <= people.length <= 5 * 104
     * 1 <= people[i] <= limit <= 3 * 104
     * 先排序，然后双指针最大和最小的，两两一组坐船
     *      如果不能一起坐船，那么重量大的先坐，count+1，right--
     *      一起坐即right++ left-- count++
     */
    public int numRescueBoats(int[] people, int limit) {
        int ans = 0;
        int n = people.length;
        Arrays.sort(people);
        int right = n - 1, left = 0;
        while (left <= right) {
            if (people[left] + people[right] <= limit) {
                left++;
            }
            right--;
            ans++;

        }
        return ans;
    }
}
